import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 涛
 * Date: 2023-10-17
 * Time: 11:43
 */
public class HashBucket {
    class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    //数组下放链表
    public static final float DEFAULT_FACTOR = 0.75f;//散链表的载荷因子
    public int usedSize;//存放数据的个数
    public Node[] array;

    public HashBucket() {
        this.array = new Node[10];
    }

    /**
     * 存放元素
     * @param key
     * @param val
     */
    public void put(int key, int val) {
        int index = key % array.length;
        //找array[index]里面是否存在key，有就更新val的值，没有就头插
        Node cur = array[index];
        while (cur != null) {
            if(cur.key == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //cur == null,链表遍历完，没有找到key
        //开始头插
        Node node = new Node(key, val);
        node.next = array[index];
        array[index] = node;
        usedSize++;
        //判断散链表的载荷因子是否达到额定值，达到就要扩容
        if(doLoadFactor() > DEFAULT_FACTOR) {
            //扩容
            resize();
        }
    }
    public float doLoadFactor() {
        return usedSize * 1.0f / array.length;
    }
    public void resize() {
        //array = Arrays.copyOf(array, 2 * array.length);
        //不能这么写，因为扩容后数组长度变成原来的两倍了，计算出来的哈希函数也不同，要重新计算哈希函数
        Node[] newArray = new Node[array.length * 2];
        //遍历原来的数组，把原来的数组元素都放进新的数组中,下标位置会变
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                //更新哈希函数，求新的index下标
                int index = cur.key % newArray.length;
                Node tmp = cur.next;
                //头插
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = tmp;
            }
        }
        array = newArray;
    }

    /**
     * 获取元素
     */
    public int  get(int key) {
        int index = key % 10;
        Node cur = array[index];
        while (cur != null) {
            //找到这下标下的key位置的值
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        //走到这就没找到，返回一个-1
        return -1;
    }
}
